package SwordFingerOffer;

import java.util.ArrayList;
import java.util.List;

public class Q54_TreeKthLargestNode {
    //二叉搜索树找第 k 大节点
    //中序遍历是递增序列
    public int kthLargest(TreeNode root, int k) {
        List<TreeNode> list = new ArrayList<>();
        midProcess(root, list);

        return list.get(list.size() - k).val;
    }

    //做一个中序遍历
    public void midProcess(TreeNode root, List<TreeNode> list) {
        if (root == null){
            return;
        }
        midProcess(root.left, list);
        list.add(root);
        midProcess(root.right, list);
    }

    public static void main(String[] args) {
        Q54_TreeKthLargestNode fun = new Q54_TreeKthLargestNode();
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(1);
        root.left.right = new TreeNode(2);
        root.right = new TreeNode(4);
        System.out.println(fun.kthLargest(root, 1));

    }


}
